#pragma once

namespace xzy
{

	template<class T>
	struct Node
	{
		Node<T>* prev;
		Node<T>* next;
		T data;


		Node(const T& x=T())
			:prev(nullptr)
			, next(nullptr)
			, data(x)
		{

		}
	};
	

	template<class T,class Ref,class pef>
	struct _list_iterator
	{
		typedef Node<T> Node;
		typedef _list_iterator<T,Ref,pef> self;
		Node* _node;

		_list_iterator(Node* node)
			:_node(node)
		{

		}

		self& operator ++()
		{
			_node = _node->next;
			return *this;
		}

		self operator ++(int)
		{
			self it = *this;
			_node = _node->next;
			return it;
		}

		Ref operator*()
		{
			return _node->data;
		}

		pef operator->()
		{
			return &_node->data;
		}

		bool operator !=(const self& list)
		{
			return _node != list._node;
		}

		self& operator --()
		{
			_node = _node->prev;
			return *this;
		}

		self operator --(int)
		{
			self it = *this;
			_node = _node->prev;
			return it;
		}
	};

	template<class T>
	class List
	{
	
		typedef Node<T> Node;
		typedef _list_iterator<T, T&,T*> iterator;
		typedef _list_iterator<T, const T&,const T*> const_iterator; 

		typedef Reverse_iterator<T, T&, T*> iterator;
		typedef Reverse_iterator<T, const T&, const T*> const_Reverse_iterator;

	public:

		void empty_init()
		{
			Node* newnode = new Node;
			_head = newnode;
			_head->next = _head;
			_head->prev = _head;
		}
		List()
		{
			
			empty_init();
		}
		List(const List<T>& ls)
		{
			empty_init();
			const_iterator it = ls.begin();
			while (it != ls.end())
			{
				
				push_back(*it);
				++it;
			}
		}
		void swap(List<T>& ls)
		{
			std::swap(_head, ls._head);
		}

		List<T>& operator=( List<T>&ls)
		{
			swap(ls);

			return *this;
		}
		iterator begin()
		{
			return _head->next;
		}
		iterator end()
		{
			return _head;
		}
		const_iterator begin()const
		{
			return _head->next;
		}
		const_iterator end()const
		{
			return _head;
		}
		void push_back(T x)
		{
			Node* newnode = new Node(x);

			Node* cur = newnode;
			Node* end = _head->prev;
			Node* prev= _head;

			end->next = cur;
			cur->next = prev;

			prev->prev = cur;
			cur->prev = prev;

		}

		iterator insert(iterator pos, T x)
		{
			Node* newnode = new Node(x);

			Node* cur = newnode;
			Node* next =pos._node;
			Node* prev = pos._node->prev;

			next->prev = cur;
			cur->next = next;

			prev->next = cur;
			cur->prev = prev;
			return pos;
		}

		void push_front(T x)
		{
			insert(begin(), x);
		}


		iterator earse(iterator pos)
		{
			Node* next = pos._node->next;
			Node* prev = pos._node->prev;

			next->prev = prev;
			prev->next = next;

			delete pos._node;

			return prev;
		}

		void pop_back()
		{
			erase(end()--);
		}

		void pop_front()
		{
			erase(begin());
		}
	private:
		Node* _head;
	};

	void test01()
	{
		List<int> list1;
		list1.push_back(1);
		list1.push_back(2);
		list1.push_back(3);
		list1.push_back(4);

		for (auto e : list1)
		{
			cout << e << " ";
		}
		cout << endl;

		auto it = list1.begin();
		while (it != list1.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;

		it--;
		cout << *it << " ";
	
		cout << endl;

		list1.insert(list1.begin() ,100);

		it = list1.begin();
		while (it != list1.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;

		list1.earse(list1.begin());

		it = list1.begin();
		while (it != list1.end())
		{
			cout << *it << " ";
			it++;
		}
		cout << endl;


	}

	void test02()
	{
		List<int> list1;
		list1.push_back(1);
		list1.push_back(2);
		list1.push_back(3);
		list1.push_back(4);
		for (auto e : list1)
		{
			cout << e << " ";
		}
		cout << endl;

		List<int> list2(list1);
		for (auto e : list2)
		{
			cout << e << " ";
		}
		cout << endl;

		List<int> list3;
		list3 = list1;
		for (auto e : list2)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}
